1. Field of the Invention
The present invention relates to algorithms and more particularly to algorithms useful in image compression.
2. Brief Description of Prior Developments
The number of systems generating multiple images of the same scene at different frequency bands and their applications have rapidly increased in the last several years. Remote sensing systems, thematic mapper sensors, and multispectral Forward Looking Infrared (FLIR) systems are only a few examples of such systems. The data product of a multispectral sensor is a stack of images for each scene referred to as a multispectral image or data cube. Each band or component of a multispectral image can be considered as a monochrome (scalar) image. Multispectral imagery provides signal diversity that can lead to more precise and accurate results than otherwise possible with traditional single spectral imagery. A major limitation of multispectral imaging systems in practice is the required manipulation and delivery of the associated massive data files. In order to store and transmit such files, very efficient compression tools are needed. Because of this need, this disclosure shall focus on a new method for lossy compression. True lossless compression is limited in performance; here, we allow the compression to be lossy but implicitly maintain control over the fidelity of the compressed imagery so we may trade off rate vs. distortion.
To date, many of the approaches for lossy multispectral image compression rely on two stages of data processing assuming that the various bands are perfectly registered. Typically, these methods first apply a 1-Dimensional Karhunen-Loève transform (KLT) along the spectral dimension leading to a set of spectrally uncorrelated eigen-images, and subsequently each of the resultant eigen-planes is compressed using a scalar image compression method such as JPEG or wavelet based compression as is disclosed in J. A. Saghri, A. G. Tescher & J. T. Reagan, “Practical transform codeing of multispectral imagery,” IEEE Signal Processing Magazine, pp. 32–43, January, 1995. The compression rate for each eigen-image is determined through a bit allocation strategy. Other 2-stage compression methods first decorrelate the data by applying a 2D frequency transform along the spatial dimensions and a 1-dimensional KLT is subsequently applied across the spectral dimension as is disclosed in D. Tretter, C. A. Bouman, “Optical transforms for multispectral and multilayer image coding,” IEEE TIP:4:296–308, March, 1995, J. N. Bradley & C. M. Brislawn; “Spectrum analysis of multispectral imagery in conjunction with wavelet/kit data compression,” Proc. ASIMOLAR Conf. 1:26–30, November, 1993; and J. Vaisey, M. Barlaud & M. Anonini, “Multispectral Image Coding Using Lattice VQ and the Wavelet Transform,” Proc. ICIP 98, Chicago, Ill., 1998. Quantization and coding is then used to encode the transform coefficients. As is also reported in “Spectrum analysis of multispectral imagery in conjunction with wavelet/klt data compression,” Proc. ASIMOLAR Conf. 1:26–30, November, 1993; and J. Vaisey, M. Barlaud & M. Anonini, “Multispectral Image Coding Using Lattice VQ and the Wavelet Transform,” Proc. ICIP 98, Chicago, Ill., 1998 at high compression rates (less than 0.2 bit/pixel/image), both methods seem to have the same performance. The two-stage approaches mentioned above, however, have three disadvantages:                1. Image decorrelation is performed in a separable fashion, first along the spectral dimension and subsequently along the spatial dimension or vice versa. The separable approach is intrinsically suboptimal as the spatial and spectral statistics are not exploited jointly;        2. The KLT is data dependent and consequently it must be computed for each image set resulting in an unacceptable amount of computation;        3. Transformed image planes after the initial decorrelation are coded independently of the others, despite of the spatial similarities across bands. The focus of this paper is to introduce a method which exploits spatial and frequency correlation jointly.        
The following example illustrates these issues. Consider a vector-valued M1×M2 multispectral image f(m))=[f1(m), f2(m), . . . , fL(m)]T with L bands. m=(m1,m2) represents a pixel's spatial position with m1=1, . . . , M1 and m2=1, . . . , M2, and 1≦k≦L is the spectral band index. The multispectral image is thus composed of M1×M2 f-vectors of length L. The image is then processed by the two-stage compression method described above, where a 1-Dimension KLT is applied along the spectral dimension. Let R=E(f(m)fT(m)) be the spectral correlation matrix and let qi and λi, i=1, . . . , L, be the eigenvectors and eigenvalues of R respectively. The KLT of f(m) along the spectral dimension is g(m)=QTf(m) where Q=[q1, q2, . . . , qL] is the L×L matrix whose columns are the eigenvectors of R. The resultant KLT coefficients form a set of images, {g1(m), g2(m), . . . , gL(M)} referred here to as eigen-images. FIG. 1 depicts the KLT of a 2-band image into a pair of decorrelated eigen-images. A three-level wavelet decomposition of each eigen-image is also shown. These images clearly show that although the eigen-images are decorrelated across bands at a particular pixel location, cross-band correlation among groups of pixels remains. The residual cross-band correlation results in a strong spatial similarity not exploited by the wavelet transforms applied to each eigen-image. In fact, FIG. 1 shows that spatial similarity remains after the wavelet transforms are applied.
An approach to overcome the shortcomings of the two-stage compression algorithm would be to design a coder that takes advantage of the intra-band and cross-band spatial similarities. A 3D (3D) zero-tree coder, for instance, can be designed to jointly exploit the intra-band and cross-band correlations inherent in a data cube as is disclosed in A. Bilgin, G. Zweig & M. W. Marcellin, “Three-dimensional Image Compression using Integer Wavelets,” Appl. Optics, 39#11:1799–1814, April, 2000. This, however, can become very complex since the number bands to be jointly encoded can be quite large. Also, the bands are typically separable in three-dimensions and the zero-tree coder spawns children at a cubic rate having implications for the production of zero-trees. Or three-dimensional data may be processed via some three-dimensional extension of a well-known transform such as the DCT G. Abousleman, M. W. Marcellin & B. Hunt, “Compression of Hyperspectral Imagery using 3-D DCT and Hybrid DPCM/DCT,” IEEE TGRS 33#1:26–34, January, 1995. Here, again, there is the question of complexity and the constraints imposed by block transformation. In reference 6, the authors back off from processing using a 3D DCT in favor of a compromise using 2D DCT and DPCM in the spectral domain.